﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>

using namespace std;

//奇偶树
//https://leetcode.cn/problems/even-odd-tree/
// typedef struct TreeNode* QDataType;
// // 链式结构：表示队列 
// typedef struct QListNode
// {
	// struct QListNode* _next;
	// QDataType _data;
// }QNode;

// // 队列的结构 
// typedef struct Queue
// {
	// QNode* _front;//头
	// QNode* _rear;//尾
	// int size;//计数
// }Queue;

// // 初始化队列 
// void QueueInit(Queue* q);
// // 队尾入队列 
// void QueuePush(Queue* q, QDataType data);
// // 队头出队列 
// void QueuePop(Queue* q);
// // 获取队列头部元素 
// QDataType QueueFront(Queue* q);
// // 获取队列队尾元素 
// QDataType QueueBack(Queue* q);
// // 获取队列中有效元素个数 
// int QueueSize(Queue* q);
// // 检测队列是否为空，如果为空返回1，如果非空返回0
// int QueueEmpty(Queue* q);
// // 销毁队列 
// void QueueDestroy(Queue* q);



// // 初始化队列 
// void QueueInit(Queue* q)
// {
	// assert(q);
	// q->_front = q->_rear = NULL;//头尾指针置空
	// q->size = 0;
// }

// // 队尾入队列 
// void QueuePush(Queue* q, QDataType data)
// {
	// assert(q);
	// QNode* newnode = (QNode*)malloc(sizeof(QNode));//申请一个新节点
	// if (!newnode)//判断是否申请成功
	// {
		// perror("malloc fail!\n");
		// exit(-1);
	// }

	// newnode->_data = data;
	// newnode->_next = NULL;

	// if (!q->_rear)//判断是否为首次插入
	// {

		// q->_front = q->_rear = newnode;//直接插入
	// }
	// else
	// {
		// q->_rear->_next = newnode;//尾指针节点的next指向新节点
		// q->_rear = newnode;//尾指针后移
	// }
	// ++(q->size);
// }

// // 队头出队列 
// void QueuePop(Queue* q)
// {
	// assert(q);//判断指针是否为空
	// if (!QueueEmpty(q))
	// {
		// if (!(q->_front == NULL && q->_rear == NULL))
		// {
			// QNode* freenode = q->_front;//存储当前的头节点方便释放
			// if ((q->_front) != (q->_rear))//判断是否为空
			// {
				// if(q->_front)
					// q->_front = q->_front->_next;//头指针后移

				// free(freenode);//释放
			// }
			// else//释放最后一个节点
			// {
				// q->_front = q->_rear = NULL;//置空指针防止野指针访问
				// free(freenode);//释放
			// }
			// --(q->size);
		// }
	// }
// }


// // 获取队列头部元素 
// QDataType QueueFront(Queue* q)
// {
	// assert(q);
	// if (!QueueEmpty(q))
	// {
		// return q->_front->_data;
	// }
	// return NULL;
// }


// // 获取队列中有效元素个数 
// int QueueSize(Queue* q)
// {
	// assert(q);

	// return q->size;

// }

// // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
// int QueueEmpty(Queue* q)
// {
	// assert(q);
	// return (q->_front == NULL && q->_rear == NULL);
// }

// // 销毁队列 
// void QueueDestroy(Queue* q)
// {
	// assert(q);
	// if (!QueueEmpty(q))
	// {
		// if (!(q->_front == NULL && q->_rear == NULL))//判断队列是否为空
		// {
			// QNode* cur = q->_front;
			// while (cur)
			// {
				// QNode* freenode = cur;
				// cur = cur->_next;
				// free(freenode);
			// }
			// q->size = 0;
		// }
	// }
// }

// bool isEvenOddTree(struct TreeNode* root)
// {
    // Queue q;
	// QueueInit(&q);// 初始化队列 
	// if (root)//判断树是否为空
	// {
		// QueuePush(&q, root);//根节点入队
        // int Dep = 0;
		// while (!QueueEmpty(&q))//队列不为空则继续循环
		// {
			// int size = QueueSize(&q);
			// while (size--)
			// {
				// QDataType BT1 = QueueFront(&q);//取一个元素出队
				// QueuePop(&q);
                // QDataType BT2 = NULL;
				// if (size != 0)
				// {
					// BT2 = QueueFront(&q);
				// }
                // if(BT1 && BT2)
                // {
					// if (Dep % 2 == 0)
					// {
						// if (BT1->val >= BT2->val || BT1->val % 2 == 0 && BT2->val % 2 == 0)
						// {
							// return false;
						// }
					// }
					// else
					// {
						// if (BT1->val <= BT2->val || BT1->val % 2 != 0 && BT2->val % 2 != 0)
						// {
							// return false;
						// }
					// }
                // }
				// else
				// {
					// if (Dep % 2 == 0)
					// {
						// if (BT1 && BT1->val % 2 == 0)
						// {
							// return false;
						// }
					// }
					// else
					// {
						// if (BT1 && BT1->val % 2 != 0)
						// {
							// return false;
						// }
					// }
				// }
                // if(BT1)
                // {
                    // if (BT1->left)//左孩子入队
				    // {
					    // QueuePush(&q, BT1->left);
				    // }
				    // if (BT1->right)//右孩子入队
				    // {
					    // QueuePush(&q, BT1->right);
				    // }
                // }
			// }
            // ++Dep;
		// }
	// }
	// QueueDestroy(&q);
    // return true;
// }











//数组的相对排序
//https://leetcode.cn/problems/relative-sort-array/

// int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)
// {
    // if(arr1Size != 0)
    // {
        // int* tmp = (int*)malloc(sizeof(int)*arr1Size);
        // int t = 0;
        // for(int i = 0; i<arr2Size; ++i)
        // {
            // int s = 0;
            // for(int k = 0; k<arr1Size; ++k)
            // {
                // if(arr1[k]==arr2[i])
                // {
                    // ++s;
                    // arr1[k]=-1;
                // }
            // }
            // while(s--)
            // {
                // tmp[t++]=arr2[i];
            // }
        // }
        // int s = 0;
        // for(int i = 0; i<arr1Size; ++i)
        // {
            // for(int k = 0; k<arr1Size-i-1; ++k)
            // {
                // if(arr1[k]>arr1[k+1])
                // {
                    // int m = arr1[k];
                    // arr1[k] = arr1[k+1];
                    // arr1[k+1]=m;
                // }
            // }
            // if(arr1[i]==-1)//记录已被排序的数据
            // {
                // ++s;
            // }
        // }
        // for(int j = s; j<arr1Size; ++j)
        // {
            // if(arr1[j]!=-1)
            // {
                // tmp[t++]=arr1[j];
            // }
        // }
        // for(int l = 0; l<arr1Size; ++l)
        // {
            // arr1[l]=tmp[l];
        // }
        // free(tmp);
    // }
    // *returnSize = arr1Size;
    // return arr1;
// }